﻿// D.Lucky Chains - 1766D.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
D - https://codeforces.com/problemset/problem/1766/D


思路
这道题拿到手不好想，因为涉及到数论知识，但是其实考察并不深入。

如果一对正整数 (x,y) 的最大公约数等于 1（gcd(x,y)=1），则把它们命名为幸运正整数 (x,y)。

我们把 (x,y) 引起的链定义为在某个整数 k≥0 时由 (x,y)，(x+1,y+1)，(x+2,y+2)，...，(x+k,y+k) 组成的序列。

如果链中的所有配对都是幸运的，我们就把这样的链命名为幸运链。

给你 n 对（xi,yi）。请为每对计算由这对引起的最长幸运链的长度。注意，如果 (xi,yi) 本身不幸运，则链的长度为 0。

输入
第一行包含一个整数 n（1≤n≤106）--线对数。

接下来的 n 行包含 n 对数据，每行一对。第 i 行包含两个整数 xi 和 yi（1≤xi<yi≤107）--对应的数据对。

输出
打印 n 个整数，其中第 i 个整数是 (xi,yi) 引发的最长幸运链的长度 或-1 如果幸运链可以无限长，则为-1。



Example
InputCopy
4
5 15
13 37
8 9
10009 20000
OutputCopy
0
1
-1
79

注释
在第一个测试案例中，gcd（5,15）=5>1，因此已经不幸运了，所以幸运链的长度为 0。
在第二个测试案例中，gcd（13+1,37+1）=gcd（14,38）=2。因此，幸运链只包含一对 (13,37)。

*/
#include <iostream>

using namespace std;

int main()
{
    std::cout << "Hello World!\n";

    return 0;
}

 